<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>概率</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="概率">概率</h1>
<ul>
<li><a href="https://cosx.org/2015/06/generating-normal-distr-variates">漫谈正态分布的生成</a></li>
</ul>
<h1 id="1-lc-497-random-point-in-non-overlapping-rectangles">1. LC 497. Random Point in Non-overlapping Rectangles</h1>
<ul>
<li><a href="https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/">https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/</a></li>
</ul>
<p>给定一组不重叠的矩阵， 实现pick()函数，从矩阵里面挑选一个整数坐标点， 要求符合正态分布。</p>
<p>很容易想到。</p>
<ol>
<li>计算矩阵面积的累加数组</li>
<li>根据面积的随机数，找到该点位于哪一个矩阵</li>
<li>再到该矩阵内部随机挑选一个点。</li>
</ol>
<p>我自己的解法</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> random
<span class="hljs-keyword">import</span> bisect
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, rects: List[List[int]])</span>:</span>
        self.n = len(rects)
        self.rects = rects
        self.areas_cum = []
        t = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> x1, y1, x2, y2 <span class="hljs-keyword">in</span> rects:
            area = (x2 - x1 + <span class="hljs-number">1</span>) * (y2 - y1 + <span class="hljs-number">1</span>)  <span class="hljs-comment"># 这里很关键，因为要包含边界上的点，所以不能是(x2-x1) * (y2-y1)</span>
            t = t + area
            self.areas_cum.append(t)
        self.area_total = t
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pick</span><span class="hljs-params">(self)</span> -&gt; List[int]:</span>
        area = random.randint(<span class="hljs-number">1</span>, self.area_total)
        pos = bisect.bisect_left(self.areas_cum, area)  <span class="hljs-comment"># 二分查找，找到对应的矩阵</span>
        x1, y1, x2, y2 = self.rects[pos]
        x_pos = random.randint(x1, x2)  <span class="hljs-comment"># 直接随机挑选一个证书点即可，最开始想复杂了。</span>
        y_pos = random.randint(y1, y2)
        <span class="hljs-keyword">return</span>(x_pos, y_pos)
</div></code></pre>
<p>别人的解法一</p>
<ul>
<li><a href="https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/discuss/154147/Python-weighted-probability-solution">https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/discuss/154147/Python-weighted-probability-solution</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, rects)</span>:</span>
        self.rects, self.ranges, sm = rects, [], <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> x1, y1, x2, y2 <span class="hljs-keyword">in</span> rects:
            sm += (x2 - x1 + <span class="hljs-number">1</span>) * (y2 - y1 + <span class="hljs-number">1</span>)
            self.ranges.append(sm)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pick</span><span class="hljs-params">(self)</span>:</span>
        x1, y1, x2, y2 = self.rects[bisect.bisect_left(self.ranges, random.randint(<span class="hljs-number">1</span>, self.ranges[<span class="hljs-number">-1</span>]))]
        <span class="hljs-keyword">return</span> [random.randint(x1, x2), random.randint(y1, y2)]
</div></code></pre>
<p>别人的解法二</p>
<ul>
<li><a href="https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/discuss/805232/Python-Short-solution-with-binary-search-explained">https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/discuss/805232/Python-Short-solution-with-binary-search-explained</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, rects)</span>:</span>
        w = [(x2-x1+<span class="hljs-number">1</span>)*(y2-y1+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> x1,y1,x2,y2 <span class="hljs-keyword">in</span> rects]
        self.weights = [i/sum(w) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> accumulate(w)]
        self.rects = rects

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pick</span><span class="hljs-params">(self)</span>:</span>
        n_rect = bisect.bisect(self.weights, random.random())
        x1, y1, x2, y2 = self.rects[n_rect] 
        <span class="hljs-keyword">return</span> [random.randint(x1, x2),random.randint(y1, y2)]
</div></code></pre>
<h1 id="2-lc-470-implement-rand10-using-rand7">2. LC  470. Implement Rand10() Using Rand7()</h1>
<ul>
<li><a href="https://leetcode.com/problems/implement-rand10-using-rand7/">https://leetcode.com/problems/implement-rand10-using-rand7/</a></li>
</ul>
<p>利用rand7()来实现rand10(), 关键就是调用rand7()两次，利用7进制来计算对应的10进制数。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">rand10</span><span class="hljs-params">(self)</span>:</span>
        <span class="hljs-string">"""
        :rtype: int
        """</span>
        <span class="hljs-keyword">while</span> <span class="hljs-literal">True</span>:
            a = rand7()
            b = rand7()
            r = (a - <span class="hljs-number">1</span>) * <span class="hljs-number">7</span> + b - <span class="hljs-number">1</span>  <span class="hljs-comment"># 注意，这里不能写成 r = a * b, 否则生成的概率不均匀</span>
            <span class="hljs-keyword">if</span> r &lt;= <span class="hljs-number">39</span>:
                <span class="hljs-keyword">return</span> r % <span class="hljs-number">10</span> + <span class="hljs-number">1</span>
            
</div></code></pre>

    </body>
    </html>